﻿using System;

namespace Binary_Tree
{
    class Tree<T> 
        where T : IComparable<T>
    {
        private TreeNode<T> root;

        public void Insert(T data)
        {
            if (root == null)
                root = new TreeNode<T>(data);
            else 
                InsertNode(root, data);
        }
        public void InsertNode(TreeNode<T> node, T data)
        {
            if (node.Data.CompareTo(data) == 1)
            {
                if (node.LeftNode == null)
                    node.LeftNode = new TreeNode<T>(data);
                else
                    InsertNode(node.LeftNode, data);
            }
            else
            {
                if (node.RightNode == null)
                    node.RightNode = new TreeNode<T>(data);
                else
                    InsertNode(node.RightNode, data);
            }
        }

        #region Tree Traversal

        public void PreorderTraversal()
        {                  
                PreorderTraversalHelp(root);   
        }

        private void PreorderTraversalHelp(TreeNode<T> node)
        {
            if (node != null)
            {
                Console.WriteLine(node.Data + " ");
                PreorderTraversalHelp(node.LeftNode);
                PreorderTraversalHelp(node.RightNode);
            }
        }

        public void InorderTraversal()
        {
            InorderTraversalHelp(root);
        }

        private void InorderTraversalHelp(TreeNode<T> node)
        {
            if (node != null)
            {                
                InorderTraversalHelp(node.LeftNode);
                Console.WriteLine(node.Data + " ");
                InorderTraversalHelp(node.RightNode);
            }
        }

        public void PostorderTraversal()
        {
            PostorderTraversalHelp(root);
        }

        private void PostorderTraversalHelp(TreeNode<T> node)
        {
            if (node != null)
            {
                PostorderTraversalHelp(node.LeftNode);
                Console.WriteLine(node.Data + " ");
                PostorderTraversalHelp(node.RightNode);
            }
        }

        #endregion

        public void LevelTraversal()
        {
            if (root == null)
                return;

            Queue<TreeNode<T>> levelQueue = new Queue<TreeNode<T>>();
            levelQueue.Enqueue(root);
            
             
            while (!levelQueue.IsEmpty())
            {
                TreeNode<T> currentNode = levelQueue.Dequeue();

                Console.Write(currentNode.Data + " ");

                if (currentNode.LeftNode != null)
                    levelQueue.Enqueue(currentNode.LeftNode);
                if (currentNode.RightNode != null)
                    levelQueue.Enqueue(currentNode.RightNode);
            }
        }

        public void OutputTree()
        {
            OutputTreeHelper(root, 0);
        }

        private void OutputTreeHelper(TreeNode<T> node, int spaces)
        {            
            while (node != null)
            {
                OutputTreeHelper(node.RightNode, spaces + 5);

                for (int i = 0; i < spaces; i++)
                    Console.Write(" ");

                Console.WriteLine(node.Data);
                
                node = node.LeftNode;
                spaces += 5;
            }
        }
    }
}
